πŸ‘©β€πŸ’» 67259. 경주둜 건섀

@Seongukbaek Posted April 30, 2022 Β· Updated April 30, 2022 Β· 6 min read

문제

κ±΄μ„€νšŒμ‚¬μ˜ 섀계사인 μ£ λ₯΄λ””λŠ” κ³ κ°μ‚¬λ‘œλΆ€ν„° μžλ™μ°¨ 경주둜 건섀에 ν•„μš”ν•œ 견적을 μ˜λ’°λ°›μ•˜μŠ΅λ‹ˆλ‹€. 제곡된 경주둜 섀계 도면에 λ”°λ₯΄λ©΄ 경주둜 λΆ€μ§€λŠ” N x N 크기의 μ •μ‚¬κ°ν˜• 격자 ν˜•νƒœμ΄λ©° 각 κ²©μžλŠ” 1 x 1 ν¬κΈ°μž…λ‹ˆλ‹€. 섀계 λ„λ©΄μ—λŠ” 각 격자의 칸은 0 λ˜λŠ” 1 둜 μ±„μ›Œμ Έ 있으며, 0은 칸이 λΉ„μ–΄ μžˆμŒμ„ 1은 ν•΄λ‹Ή 칸이 벽으둜 μ±„μ›Œμ Έ μžˆμŒμ„ λ‚˜νƒ€λƒ…λ‹ˆλ‹€. 경주둜의 μΆœλ°œμ μ€ (0, 0) μΉΈ(쒌츑 상단)이며, 도착점은 (N-1, N-1) μΉΈ(우츑 ν•˜λ‹¨)μž…λ‹ˆλ‹€. μ£ λ₯΄λ””λŠ” 좜발점인 (0, 0) μΉΈμ—μ„œ μΆœλ°œν•œ μžλ™μ°¨κ°€ 도착점인 (N-1, N-1) μΉΈκΉŒμ§€ λ¬΄μ‚¬νžˆ 도달할 수 있게 쀑간에 λŠκΈ°μ§€ μ•Šλ„λ‘ 경주둜λ₯Ό 건섀해야 ν•©λ‹ˆλ‹€. κ²½μ£Όλ‘œλŠ” 상, ν•˜, 쒌, 우둜 μΈμ ‘ν•œ 두 빈 칸을 μ—°κ²°ν•˜μ—¬ 건섀할 수 있으며, 벽이 μžˆλŠ” μΉΈμ—λŠ” 경주둜λ₯Ό 건섀할 수 μ—†μŠ΅λ‹ˆλ‹€. μ΄λ•Œ, μΈμ ‘ν•œ 두 빈 칸을 μƒν•˜ λ˜λŠ” 쒌우둜 μ—°κ²°ν•œ 경주둜λ₯Ό 직선 λ„λ‘œ 라고 ν•©λ‹ˆλ‹€. λ˜ν•œ 두 직선 λ„λ‘œκ°€ μ„œλ‘œ 직각으둜 λ§Œλ‚˜λŠ” 지점을 μ½”λ„ˆ 라고 λΆ€λ¦…λ‹ˆλ‹€. 건섀 λΉ„μš©μ„ 계산해 λ³΄λ‹ˆ 직선 λ„λ‘œ ν•˜λ‚˜λ₯Ό λ§Œλ“€ λ•ŒλŠ” 100원이 μ†Œμš”λ˜λ©°, μ½”λ„ˆλ₯Ό ν•˜λ‚˜ λ§Œλ“€ λ•ŒλŠ” 500원이 μΆ”κ°€λ‘œ λ“­λ‹ˆλ‹€. μ£ λ₯΄λ””λŠ” κ²¬μ μ„œ μž‘μ„±μ„ μœ„ν•΄ 경주둜λ₯Ό κ±΄μ„€ν•˜λŠ” 데 ν•„μš”ν•œ μ΅œμ†Œ λΉ„μš©μ„ 계산해야 ν•©λ‹ˆλ‹€.

예λ₯Ό λ“€μ–΄, μ•„λž˜ 그림은 직선 λ„λ‘œ 6κ°œμ™€ μ½”λ„ˆ 4개둜 κ΅¬μ„±λœ μž„μ˜μ˜ 경주둜 μ˜ˆμ‹œμ΄λ©°, 건섀 λΉ„μš©μ€ 6 x 100 + 4 x 500 = 2600원 μž…λ‹ˆλ‹€.

또 λ‹€λ₯Έ 예둜, μ•„λž˜ 그림은 직선 λ„λ‘œ 4κ°œμ™€ μ½”λ„ˆ 1개둜 κ΅¬μ„±λœ 경주둜이며, 건섀 λΉ„μš©μ€ 4 x 100 + 1 x 500 = 900원 μž…λ‹ˆλ‹€.

λ„λ©΄μ˜ μƒνƒœ(0은 λΉ„μ–΄ 있음, 1은 λ²½)을 λ‚˜νƒ€λ‚΄λŠ” 2차원 λ°°μ—΄ boardκ°€ λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§ˆ λ•Œ, 경주둜λ₯Ό κ±΄μ„€ν•˜λŠ”λ° ν•„μš”ν•œ μ΅œμ†Œ λΉ„μš©μ„ return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μ™„μ„±ν•΄μ£Όμ„Έμš”.

μ œν•œμ‚¬ν•­

  • boardλŠ” 2차원 정사각 λ°°μ—΄λ‘œ λ°°μ—΄μ˜ ν¬κΈ°λŠ” 3 이상 25 μ΄ν•˜μž…λ‹ˆλ‹€.
  • board λ°°μ—΄μ˜ 각 μ›μ†Œμ˜ 값은 0 λ˜λŠ” 1 μž…λ‹ˆλ‹€.

    • λ„λ©΄μ˜ κ°€μž₯ μ™Όμͺ½ 상단 μ’Œν‘œλŠ” (0, 0)이며, κ°€μž₯ 우츑 ν•˜λ‹¨ μ’Œν‘œλŠ” (N-1, N-1) μž…λ‹ˆλ‹€.
    • μ›μ†Œμ˜ κ°’ 0은 칸이 λΉ„μ–΄ μžˆμ–΄ λ„λ‘œ 연결이 κ°€λŠ₯함을 1은 칸이 벽으둜 μ±„μ›Œμ Έ μžˆμ–΄ λ„λ‘œ 연결이 λΆˆκ°€λŠ₯함을 λ‚˜νƒ€λƒ…λ‹ˆλ‹€.
  • boardλŠ” 항상 μΆœλ°œμ μ—μ„œ λ„μ°©μ κΉŒμ§€ 경주둜λ₯Ό 건섀할 수 μžˆλŠ” ν˜•νƒœλ‘œ μ£Όμ–΄μ§‘λ‹ˆλ‹€.
  • 좜발점과 도착점 칸의 μ›μ†Œμ˜ 값은 항상 0으둜 μ£Όμ–΄μ§‘λ‹ˆλ‹€.

μž…μΆœλ ₯ 예

board result
[0,0,0],[0,0,0],[0,0,0] 900
[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0] 3800
[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0] 2100
[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[0,1,0,0,0,1],[0,0,0,0,0,0] 3200

πŸ“ Logic

private void dfs(int[][] board, int prevDir, int x, int y) { if (x == n - 1 && y == n - 1) { minCost = Math.min(costs[x][y], minCost); return; } for (int i = 0; i < 4; i++) { int nx = x + xDir[i]; int ny = y + yDir[i]; if (nx == 0 && ny == 0) continue; if (!checkBoundary(nx, ny)) continue; if (board[nx][ny] == 1) continue; int tmp = costs[x][y]; if (prevDir != -1 && Math.abs(prevDir - i) % 2 == 1) tmp += 500; tmp += 100; if ((costs[nx][ny] != 0 && costs[nx][ny] >= tmp) || costs[nx][ny] == 0) { costs[nx][ny] = tmp; dfs(board, i, nx, ny); } } }
  • prevDir 을 μ‚¬μš©ν•΄ 이전 λ°©ν–₯을 μ €μž₯ν•˜κ³ , 직선인지 μ½”λ„ˆμΈμ§€ νŒλ‹¨ν•œλ‹€.
  • 탐색 λ°©ν–₯에 μš°μ„ μˆœμœ„λ₯Ό 두고, λ¨Όμ € νƒμƒ‰ν•œλ‹€.

    • λΉ„μš©μ΄ 더 μž‘μ€ 경우의 κ±΄μ„€λ§Œμ„ updateν•˜λ„λ‘ ν•œλ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Solution { int[] xDir = { 0, 1, 0, -1 }; int[] yDir = { 1, 0, -1, 0 }; int[][] costs; int n; int minCost = Integer.MAX_VALUE; public int solution(int[][] board) { costs = new int[board.length][board.length]; n = board.length; dfs(board, -1, 0, 0); return minCost; } private void dfs(int[][] board, int prevDir, int x, int y) { if (x == n - 1 && y == n - 1) { minCost = Math.min(costs[x][y], minCost); return; } for (int i = 0; i < 4; i++) { int nx = x + xDir[i]; int ny = y + yDir[i]; if (nx == 0 && ny == 0) continue; if (!checkBoundary(nx, ny)) continue; if (board[nx][ny] == 1) continue; int tmp = costs[x][y]; if (prevDir != -1 && Math.abs(prevDir - i) % 2 == 1) tmp += 500; tmp += 100; if ((costs[nx][ny] != 0 && costs[nx][ny] >= tmp) || costs[nx][ny] == 0) { costs[nx][ny] = tmp; dfs(board, i, nx, ny); } } } private boolean checkBoundary(int x, int y) { return (x < n && x >= 0 && y < n && y >= 0); } }

✏️ Review

  • 생각 μ™Έλ‘œ, κ°„λ‹¨ν•œ DFS λ¬Έμ œμ˜€λ‹€. 이전 λ°©ν–₯을 DFS의 인자둜 μ „λ‹¬ν•΄μ£ΌλŠ” 것이 μ€‘μš”ν–ˆλ˜ 것 κ°™λ‹€.

πŸ“• 좜처

Programmers : https://programmers.co.kr/learn/courses/30/lessons/67259

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€